﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{

    class Quicksort<C>
    {
  

        public List<C> sort(List<C> list, int left, int right, Func<C,C, int> comp)
        {
            int l = left;
            int r = right;
         
            C pivot = list[l];
            C tmp;        

            while (l <= r)
            {
                while (comp(list[l], pivot) < 0)
                {
                    l++;
                }
                while (comp(list[r], pivot) > 0)
                {
                    r--;
                }
                if (l <= r)
                {
                    tmp = list[l];
                    list[l++] = list[r];
                    list[r--] = tmp;
                }
            }
            if (left < r)
            {
                sort(list, left, r, comp);
            }
            if (l < right)
            {
                sort(list, l, right, comp);
            }

            return list;
        }


        //public List<C> sort(List<C> list, int left, int right, Func<C, int> comp)
        //{
        //    int l = left;
        //    int r = right;

        //    int pivot = comp(list[l]);
        //    C tmp;

        //    while (l <= r)
        //    {
        //        while (comp(list[l]) < pivot)
        //        {
        //            l++;
        //        }
        //        while (pivot < comp(list[r]))
        //        {
        //            r--;
        //        }
        //        if (l <= r)
        //        {
        //            tmp = list[l];
        //            list[l++] = list[r];
        //            list[r--] = tmp;
        //        }
        //    }
        //    if (left < r)
        //    {
        //        sort(list, left, r, comp);
        //    }
        //    if (l < right)
        //    {
        //        sort(list, l, right, comp);
        //    }

        //    return list;
        //}
    }
}
